package com.zwj.interview.排序;

import java.util.Arrays;
import java.util.Random;

/**
 * 快速排序：
 * <p>
 * 排序过程如下：在输入数组中随机选取一个元素作为中间值（pivot），
 * 然后对数组进行分区（partition），使所有比中间值小的数据移到数组的左边，
 * 所有比中间值大的数据移到数组的右边。接下来对中间值左右两侧的子数组用相同的步骤排序，直到子数组中只有一个数字为止。
 */
public class 快速排序 {

    public int[] sortArray(int[] nums) {
        quicksort(nums, 0, nums.length - 1);
        return nums;
    }


    public void quicksort(int[] nums, int start, int end) {
        if (end > start) {
            int pivot = partition(nums, start, end);
            quicksort(nums, start, pivot - 1);
            quicksort(nums, pivot + 1, end);
        }
    }



    /**
     * @param nums
     * @param start
     * @param end
     * @return 这个分区的过程很重要，我们来分析一下这个过程：
     * <p>
     * 下面以数组[4，1，5，3，6，2，7，8]为例分析分区的过程。假设数字3被随机选中称为中间值，该数字被交换到数组的尾部
     * 1、初始化两个指针，指针P1初始化至下标为-1的位置，指针P2初始化至下标为0的位置
     *      4， 1，5，6，2，7，8，3
     *  p1  p2
     * 2、始终将指针P1指向已经发现的最后一个小于3的数字。此时尚未发现任何一个小于3的数字，因此将指针P1指向一个无效的位置
     * 3、将指针P2从下标为0的位置开始向右扫描数组中的每个数字。当指针P2指向第1个小于3的数字1时，指针P1向右移动一格，
     * 然后交换两个指针指向的数字，此时数组（即两个指针）的状态如下：
     * 1，  4，5，6，2，7，8，3
     * p1  p2
     * 4、继续右移指针P2直到遇到下一个小于3的数字2，指针P1再次向右移动一格，然后交换两个指针指向的数字，
     * 此时数组（即两个指针）的状态如下：
     * 1 ，2 ，5， 6 ，4，7，8，3
     * p1        p2
     * 5、继续右移指针P2直到指向数字3也没有遇到新的小于3的数字，此时整个数组都已经扫描完毕。
     * 再次将指针P1向右移动一格，然后交换指针P1和P2指向的数字，于是所有小于3的数字都位于3的左边，
     * 所有大于3的数字都位于数组的右边
     * <p>
     * 1，2 ，3，6，4，7，8，5
     *   p1       p2
     * <p>
     * 变量small相当于指针P1，它始终指向已经发现的最后一个小于中间值的数字。而for循环中的变量i相当于指针P2，
     * 它从左到右扫描整个数组。函数partition先将随机选取的中间值交换到数组的尾部，最后又将它交换到合适的位置，
     * 使比它小的数字都在它的左边，比它大的数字都在它的右边。函数partition的返回值是中间值的最终下标
     */
    private int partition(int[] nums, int start, int end) {
        int random=new Random().nextInt(end-start+1)+start;
        //将随机选出的种子和末尾的进行交换
        swap(nums,random,end);
        //定义两个指针
        //p1开始指向-1，p2开始指向下标为0的位置，不断的移动P2,直到发现比random小的数字，移动p1,交换p1,p2处的数字
        int p1=start-1;
        //不断推进p2的指针
        for(int p2=start;p2<end;p2++){
            //找到小于end处的数字了，那么就移动p1,然后交换p1,p2处的数字
            if(nums[p2]<nums[end]){
                p1++;
                swap(nums,p2,p1);
            }
        }
        //走到这里，说明扫描完了一轮数组，那么移动p1,交换p1和尾部的数字,此时p2就指向了尾部
        p1++;
        swap(nums,p1,end);
        return p1;
    }



    /**
     * 交换数组中两个下标的值
     *
     * @param nums
     * @param index1
     * @param index2
     */
    private void swap(int[] nums, int index1, int index2) {
        if (index1 != index2) {
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
    }


    public static void main(String[] args) {
        System.out.println(Arrays.toString(new 快速排序().sortArray(new int[]{4,1,5,3,6,2,7,8})));
    }


}
